# JZ7 斐波那契数列
#
# 描述
# 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
# n≤39
#
# 示例1
# 输入：
# 4
# 返回值：
# 3

# 核心代码模式
# -*- coding:utf-8 -*-
# 斐波拉契数列的定义（即 f(n)=f(n-1)+f(n−2)）
class Solution:
    def Fibonacci(self, n):
        # write code here
        # 思路1：递归
        if n==0: return 0
        elif n==1: return 1
        if n==0 or n==1:  return n
        else: return self.Fibonacci(n-1)+self.Fibonacci(n-2)
#         时间复杂度达到O(2^(n)，且空间复杂度也有O(n)
        # 思路2：动态规划
        # 模型 多阶段决策最优解模型 ->递归 通过子问题解法推导最优解法
        # 特征 前能推导后   当前仅跟上一层有关   存在重复节点
        if n<2: return n
        a,b  = 0,1
        for i in range(2,n+1):  # 左闭右开 统一标号 n=4时 b=f(4)
            a,b = b,a+b  # 状态转移方程  这种格式两种赋值同时进行
        return b
#         时间复杂度：O(n) (根据状态转移方程和边界条件，可以得到时间复杂度 O(n))
#         空间复杂度：O(n) (同上)
